#include <vector>
using namespace std;
/*
 * @lc app=leetcode.cn id=34 lang=cpp
 *
 * [34] 在排序数组中查找元素的第一个和最后一个位置
 */

// @lc code=start
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.size() == 0) return {-1, -1};
        int l = -1, u = nums.size() - 1, first = -1, second = -1;
        // ( ] lower_bound
        while (u - l > 1) {
            int middle = (l + u) / 2;
            if (nums[middle] < target) l = middle;
            else u = middle;
        }
        if (nums[u] == target) first = u;
        // [ ) upper bound
        l = 0, u = nums.size();
        while (u - l > 1) {
            int middle = (l + u) / 2;
            if (nums[middle] > target) u = middle;
            else l = middle;
        }
        if (nums[l] == target) second = l;
        return {first, second};
    }
};
// @lc code=end

